FIGS. 1A and 1B illustrate two prior art techniques for calling or invoking a function. As used herein, a “function” describes a polymorphic or monomorphic procedure, subroutine or method. A polymorphic function has more than one implementation in a running program and a monomorphic function has a single implementation. For example, if a class A defines a function foo, and there are no subclasses of that class that also define foo, then foo is a monomorphic function. Alternatively, foo can be defined outside of a class. For example, foo may be defined at a first namespace scope. If there are no other definitions of foo in namespace scopes nested with the first scope, then foo is monomorphic. If a subclass of A (or a nested scope) defines foo, then foo is polymorphic since foo has more than one implementation in A's class lineage (or in the namespace hierarchy).
In the computing arts, and for the purposes of these discussions, an object can be defined as an instance of a class. A function can be invoked on an object directly or through a reference to the object. A reference to an object, function or other entity can be a relative, absolute or symbolic location of the entity in a memory location or a data structure.
FIGS. 1A and 2 illustrate a prior art cache-based polymorphic function call dispatching technique. Cache-based dispatching is used, for example, in applications written in the Objective-C programming language. Typically, each class can have an associated function cache and a dispatcher table (“dtable”) which are shared by all instances of the class. The dtable is a table or a list of functions defined by the class. An object reference 102 and a selector 104 are used to invoke a function identified by the selector 104. A selector, as used herein, is a sequence of one or more letters, numbers or symbols. In one implementation, a selector includes a function name and the function's argument types. The object reference 102 is used to locate the object's class definition 108 (step 202). A determination is made as to whether the selector 104 is found in a cache 110 associated with the class definition 108 (step 204). The cache contains function references for functions that have been previously invoked. If the selector 104 is found in the cache 110, the function reference 112 associated with the selector 104 in the cache 10 is used to invoke the function (step 210).
If the selector 104 is not found in the cache 110, a dtable 114 associated with the class definition 108 is searched using the selector 104. The dtable is searched for the selector 104 (step 206). If the selector 104 is not found, the sought after function is not defined for the class 108 in which case the process repeats using a parent class (e.g., 106; step 212) until a class defining the function is found. If the selector 104 is found, the function reference 112 associated with the selector 104 in the dtable 114 is added to the cache 110 (step 208) and used to invoke the function (step 210). If the cache 110 does not exist, the cache may be created first. Subsequent invocations of the function can use the cache 110 to obtain the function reference 112.
FIGS. 1B and 3 illustrate a prior art virtual function table (“vtable”) polymorphic function call dispatching technique which is used, for example, in applications written in the C++ programming language. The vtable 124 is an array of function references. Typically, there is one vtable per class definition (i.e., all instances of a class share the class's vtable). To dispatch a function call a vtable reference 120 is obtained (step 302) and an offset 122 into the vtable is added to the vtable reference 120 (step 304). The sum (i.e., offset plus vtable reference) yields a location in the vtable 124 containing the particular function reference 112 which is used to invoke the function (step 306).
Each of these function call dispatching techniques has advantages and disadvantages. The cache-based technique saves runtime memory by not creating a cache for a class until a function for the class is actually invoked and only storing function references in the cache when the corresponding functions are invoked. However, invoking functions using the cache-based technique can be slower than the vtable based technique, which only involves adding two values and dereferencing the result. This is especially noticeable for frequently called functions. But the vtable based technique can waste memory since each class has a vtable whether or not any of the class's functions are invoked. Moreover, if there are a large number of classes that override the functions of other classes, vtables can become quite large.